package leetcode.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Lc1268 {

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>();
        Arrays.sort(products);
        for (int i = 0; i < searchWord.length(); i++) {
            String sub = searchWord.substring(0, i + 1);
            List<String> tmp = new ArrayList<>();
            for (int j = 0; j < products.length; j++) {
                if (products[j].startsWith(sub)) {
                    tmp.add(products[j]);
                }
                if (tmp.size() == 3) break;
            }
            if (tmp.size() == 0) {
                while (i++ < searchWord.length()) ans.add(new ArrayList<>());
                break;
            }
            ans.add(tmp);
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc1268 lc1268 = new Lc1268();
        String[] s1 = {"havana"};
        String s2 = "1havana";
        System.out.println(lc1268.suggestedProducts(s1, s2));
    }

}
